package com.zjsru.leetcode75.level1;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: cookLee
 * @Date: 2024-01-01
 * 省份数量
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 */
public class FindCircleNum {

    /**
     * 主
     * \
     * 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
     * 输出：2
     * \
     * 输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
     * 输出：3
     * \
     * @param args args
     */
    public static void main(String[] args) {
        FindCircleNum findCircleNum = new FindCircleNum();
        int[][] isConnected = new int[][]{{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
        System.out.println(findCircleNum.findCircleNum(isConnected));
    }

    /**
     * 查找圆num
     * bfs
     * @param isConnected 已连接
     * @return int
     */
    public int findCircleNum(int[][] isConnected) {
        int len = isConnected.length;
        int ans = 0;
        //存储到连接相同的省份
        boolean[] booleans = new boolean[len];
        //链表存储下标
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            if (!booleans[i]) {
                queue.offer(i);
                while (!queue.isEmpty()) {
                    //当队列非空时，出队列一个省份索引
                    int j = queue.poll();
                    //将该省份标记为已访问
                    booleans[j] = true;
                    //所有与当前省份连接但尚未访问的省份入队列
                    for (int k = 0; k < len; k++) {
                        if (isConnected[j][k] == 1 && !booleans[k]) {
                            queue.offer(k);
                        }
                    }
                }
                ans++;
            }
        }
        return ans;
    }

    /**
     * 查找圆num2
     * dfs
     * @param isConnected 已连接
     * @return int
     */
    public int findCircleNum2(int[][] isConnected) {
        int len = isConnected.length;
        boolean[] booleans = new boolean[len];
        int ans = 0;
        for (int i = 0; i < len; i++) {
            if(!booleans[i]){
                this.dfs(isConnected,booleans,len,i);
                ans++;
            }
        }
        return ans;
    }

    /**
     * dfs
     *
     * @param isConnected 已连接
     * @param booleans    布尔值
     * @param len         len
     * @param i           我
     */
    private void dfs(int[][] isConnected, boolean[] booleans, int len, int i) {
        for (int j = 0; j < len; j++) {
            if (isConnected[i][j] == 1 && !booleans[j]) {
                booleans[j] = true;
                this.dfs(isConnected, booleans, len, j);
            }
        }
    }

}
